package com.su.test;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class NumCode {
    private int length = 9;                 //数码长度，可以处理非八数码，例如十五数码
    private int row = 3;                        //行数
    private int col = 3;                        //列数
    private int initArr[];              //初始状态的八数码
    private int targetArr[];            //目标状态的八数码

    private long time;                  //记录程序运行时间

    private Strategy strategy;

    public NumCode() {
    }

    public NumCode(int[] initArr, int[] targetArr) throws Exception {
        setInitArr(initArr);
        setTargetArr(targetArr);
    }

    public NumCode(int row, int col, int[] initArr, int[] targetArr) throws Exception {
        setRowAndCol(row,col);
        setInitArr(initArr);
        setTargetArr(targetArr);
    }

    //设置列数和行数
    public void setRowAndCol(int row,int col){
        this.row = row;
        this.col = col;
        this.length = row * col;
    }

    //其实还应该检验输入的数据是否符合情况
    public void setInitArr(int[] initArr) throws Exception {

        if(initArr.length != length)
            throw new Exception("起始数组长度错误!规定长度"+length+",起始数组长度"+initArr.length);
        this.initArr = initArr;

    }

    public void setTargetArr(int[] targetArr) throws Exception {

        if(targetArr.length != length)
            throw new Exception("目标数组长度错误!规定长度"+length+",目标数组长度"+targetArr.length);
        this.targetArr = targetArr;

    }

    /**
     * @Description 通过求逆序值，判断是否有解
     * @return true有解，false无解
     **/
    private boolean isSolveable(){
        int reverse = 0;
        for(int i=0;i<length;i++){
            for(int j=0;j<i;j++){
                if(initArr[i] != 0){
                    if(initArr[j] > initArr[i])
                        reverse++;
                }
                if(targetArr[i] != 0){
                    if(targetArr[j] > targetArr[i])
                        reverse++;
                }

            }
        }
        if(reverse % 2 == 0)
            return true;
        return false;
    }


    public void run() throws Exception {
        this.strategy.setLength(length);
        this.strategy.setCol(col);
        this.strategy.setInitArr(initArr);
        this.strategy.setTargetArr(targetArr);
        if(targetArr.length != length)
            throw new Exception("目标数组长度错误!规定长度"+length+",目标数组长度"+targetArr.length);
        if(targetArr.length != length)
            throw new Exception("目标数组长度错误!规定长度"+length+",目标数组长度"+targetArr.length);
        //如果无解
/*
        if(!isSolveable())
            return;
*/

//        long startTime = System.nanoTime();
        long startTime = System.currentTimeMillis();
        strategy.run();
//        long endTime = System.nanoTime();
        long endTime = System.currentTimeMillis();
//        time = (endTime - startTime) / 1000;
        time = endTime - startTime;


    }

    /**
     * @Description 将一个一维数组打印成二维数组
     * @param arr   一维数组
     * @return
     **/
    private void print(int []arr){
        for (int j = 0; j < this.row; j++) {
            for (int k = 0; k < this.col; k++) {
                System.out.printf("%3d",arr[j * this.col + k]);
            }
            System.out.println();
        }
    }
    public void show() throws Exception {
        System.out.println("初始数码：");
        print(initArr);
        System.out.println("目标数码：");
        print(targetArr);

        Node curNode = strategy.getLastNode();
        if (curNode== null){
            System.out.println("无解");
            return;
        }
        List<int[]> path = new ArrayList<>();
        while (curNode != null){
            path.add(curNode.num);
            curNode = curNode.parent;
        }

        for (int i = path.size()-1,index = 0; i >= 0; i--,index++) {
            System.out.println("Step(" + index + "):");
            print(path.get(i));
        }
        System.out.println("----------------------------------------------------");
    }

    /**
     * @Description     生成目标数组
     * @param n
     * @return
     **/
    public int[] generateTargetArr(int n) throws Exception {
        if(this.initArr == null){
            throw new Exception("初始数组为空");
        }
        int targetArr[] = new int[length];
        System.arraycopy(this.initArr,0,targetArr,0,length);
        int lastEmptyIndex = -1;    //记录上一次空格的位置，避免又回到原来位置
        int curEmptyIndex = 0;
        for (int i = 0; i < this.initArr.length; i++) {
            if(this.initArr[i] == 0){
                curEmptyIndex = i;
                break;
            }
        }
        int positions[] = new int[4];   //记录空格可以移动的方向 -1 左 ; 1 右 ; -col 上 ; col 下
        int len;
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            len = 0;

            //左移
            if(curEmptyIndex % this.col > 0 && curEmptyIndex -1 != lastEmptyIndex){
                positions[len++] = -1;
            }
            //上移
            if(curEmptyIndex > this.col && curEmptyIndex - this.col != lastEmptyIndex){
                positions[len++] = -this.col;
            }
            //右移
            if(curEmptyIndex % this.col < this.col - 1 && curEmptyIndex + 1 != lastEmptyIndex){
                positions[len++] = 1;
            }
            //下移
            if (curEmptyIndex < length - this.col && curEmptyIndex + this.col != lastEmptyIndex) {
                positions[len++] = this.col;
            }
            int offset = positions[random.nextInt(len)];

            int temp = targetArr[curEmptyIndex + offset];
            targetArr[curEmptyIndex + offset] = 0;
            targetArr[curEmptyIndex] = temp;
            lastEmptyIndex = curEmptyIndex;
            curEmptyIndex += offset;


        }
        return targetArr;
    }

    public void setStrategy(Strategy strategy) {
        this.strategy = strategy;
    }
    public int getSteps(){
       return strategy.getSteps();
    }

    public long getTime() {
        return time;
    }

    public int getBestSteps(){
        Node curNode = strategy.getLastNode();
        if (curNode== null){
            System.out.println("无解");
            return 0;
        }
        int sum = -1;
        while (curNode != null){
            curNode = curNode.parent;
            sum++;
        }
        return sum;
    }
}

